package kyssion.leetcode.num201_250;

import java.util.HashMap;
import java.util.Map;
import java.util.TreeSet;

/**
 * 给定一个整数数组，判断数组中是否有两个不同的索引 i 和 j，
 * 使得 nums [i] 和 nums [j] 的差的绝对值最大为 t，并且 i 和 j 之间的差的绝对值最大为 ķ。
 * <p>
 * 示例 1:
 * <p>
 * 输入: nums = [1,2,3,1], k = 3, t = 0
 * 输出: true
 * 示例 2:
 * <p>
 * 输入: nums = [1,0,1,1], k = 1, t = 2
 * 输出: true
 * 示例 3:
 * <p>
 * 输入: nums = [1,5,9,1,5,9], k = 2, t = 3
 * 输出: false
 */
public class code219_存在重复数字3 {

    public static void main(String[] args) {
        System.out.println(new code219_存在重复数字3().containsNearbyAlmostDuplicate3(
                new int[]{
                        1, 5, 9, 1, 5, 9
                }, 2, 3
        ));
    }

    /**
     * 这个思路非常好啊,设置一个标记变量,用来同步当前值和差值的比来判断k时候符合要求
     *
     * @param nums
     * @param k
     * @param t
     * @return
     */
    public boolean containsNearbyAlmostDuplicate2(int[] nums, int k, int t) {
        if (k < 1 || t < 0)
            return false;
        int n = nums.length;
        int gap = Math.max(1, t);
        long min = Integer.MAX_VALUE;
        for (int x : nums) {
            min = Math.min(min, x);
        }
        Map<Long, Integer> buckets = new HashMap<>();
        for (int i = 0; i < n; i++) {
            if (i > k) {
                long bucket = (nums[i - k - 1] - min) / gap;
                buckets.remove(bucket);
            }
            long bucket = (nums[i] - min) / gap;
            if (buckets.containsKey(bucket)
                    || (buckets.containsKey(bucket - 1) && buckets.get(bucket - 1) + t == nums[i])
                    || (buckets.containsKey(bucket + 1) && buckets.get(bucket + 1) - t == nums[i])) {
                return true;
            }
            buckets.put(bucket, nums[i]);
        }
        return false;
    }

    /**
     * 构建 BSF树解决问题
     *
     * @param nums
     * @param k
     * @param t
     * @return
     */
    public boolean containsNearbyAlmostDuplicate3(int[] nums, int k, int t) {
        // 滑动窗口结合查找表，此时滑动窗口即为查找表本身（控制查找表的大小即可控制窗口大小）
        TreeSet<Long> set = new TreeSet<>();
        for (int i = 0; i < nums.length; i++) {
            // 边添加边查找
            // 查找表中是否有大于等于 nums[i] - t 且小于等于 nums[i] + t 的值
            Long ceiling = set.ceiling((long) nums[i] - (long) t);
            if (ceiling != null && ceiling <= ((long) nums[i] + (long) t)) {
                return true;
            }
            // 添加后，控制查找表（窗口）大小，移除窗口最左边元素
            set.add((long) nums[i]);
            if (set.size() == k + 1) {
                set.remove((long) nums[i - k]);
            }
        }
        return false;
    }


    /**
     * 二重快速排序解决问题
     * @param nums
     * @param k
     * @param t
     * @return
     */
    public boolean containsNearbyAlmostDuplicate4(int[] nums, int k, int t){

        return false;
    }
}
